package com.autumn.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 两数之和
 * 给定一个整数数组nums和一个整数目标值target，在该数组中找出和 为目标值 target的那 两个 整数，并返回它们的数组下标
 * 可假设每种输入只对应一个答案，但数组中同一个元素在答案里不能重复出现
 */
public class Algorithm03Sum {
    /**
     * 穷举法
     */
    public static int[] twoSum1(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }

    /**
     * map存取
     */
    public static int[] twoSum2(int[] nums, int target) {
        //key为元素值，value为每个元素对应下标
        Map<Integer, Integer> storeNums = new HashMap<>(nums.length, 1);
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int another = target - nums[i];
            Integer anotherIndex = storeNums.get(another);
            if (null != anotherIndex) {
                result[0] = anotherIndex;
                result[1] = i;
                break;
            } else {
                storeNums.put(nums[i], i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {21, 215, 2216, 721, 21, 2321, 521, 1121};
        int target = 1642;
        long start1 = System.currentTimeMillis();
        int[] arr1 = twoSum1(nums, target);
        long end1 = System.currentTimeMillis();
        System.out.println("两个整数的下标分别为：" + arr1[0] + "、" + arr1[1] + "，耗时：" + (end1 - start1));
        System.out.println("=======================================================");
        long start2 = System.currentTimeMillis();
        int[] arr2 = twoSum2(nums, target);
        long end2 = System.currentTimeMillis();
        System.out.println("两个整数的下标分别为：" + arr2[0] + "、" + arr2[1] + "，耗时：" + (end2 - start2));
    }
}
